//
//  Subsets.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/24.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  面试题 08.04. 幂集 中等

/*
 幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

 说明：解集不能包含重复的子集。

 示例:

  输入： nums = [1,2,3]
  输出：
 [
   [3],
   [1],
   [2],
   [1,2,3],
   [1,3],
   [2,3],
   [1,2],
   []
 ]

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/power-set-lcci
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import UIKit

class Subsets: NSObject {
    
    var resultArr:[[Int]]! = []
    
    func subsets(_ nums: [Int]) -> [[Int]] {

        self.dfs(0, [], nums)
        
        //resultArr.removeFirst()
        
        return resultArr
    }
    
    
    func dfs(_ startIndex:Int, _ tmpArr:[Int], _ sourceArr:[Int]){
        
        var arr = tmpArr
        resultArr.append(arr)

        for index in startIndex ..< sourceArr.count{
            
            arr.append(sourceArr[index])
            self.dfs(index + 1, arr, sourceArr)
            arr.removeLast()
            
        }
    }
    
    
}
